import java.util.*;

class Solution {
    static class Stack1{
        public int[] elem;
        public int usedSize;
        public Stack1() {
            this.elem = new int[10];
        }
    }
    /*2:有效的括号
    * 括号匹配问题*/
    public boolean isValid(String s) {
        if (s==null)return false;
        Stack<Character> stack=new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)=='('){
                stack.push(')');
            }else if(s.charAt(i)=='['){
                stack.push(']');
            }else if(s.charAt(i)=='{') {
                stack.push('}');
            }else if(stack.isEmpty()||s.charAt(i)!=stack.pop())return false;
        }
        return stack.isEmpty();
    }
    /* 3：逆波兰表达式求值
    * 后缀表达式转中缀*/
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for (String x:tokens) {
            if (!isOperation(x)){
                stack.push(Integer.parseInt(x));
            }else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (x) {
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    private boolean isOperation(String x){
        if(x.equals("+") || x.equals("-") || x.equals("/")||x.equals("*")) {
            return true;
        }
        return false;
    }
    /*3:栈的压入、弹出序列
    输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序
    * */
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack=new Stack<>();
        int j=0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j< popA.length&&!stack.isEmpty()&&stack.peek()==popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
    /*4：最长有效括号
    * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度
    * my:始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，
    * 这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标*/
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }


}